HW_SOURCE_FILE = __file__


def num_eights(x):
    """Returns the number of times 8 appears as a digit of x.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AugAssign'])
    True
    """
    if x < 10:
        return 1 if x == 8 else 0
    return num_eights(x // 10) + (1 if x % 10 == 8 else 0)


def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(8)
    8
    >>> pingpong(10)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    -2
    >>> pingpong(30)
    -2
    >>> pingpong(68)
    0
    >>> pingpong(69)
    -1
    >>> pingpong(80)
    0
    >>> pingpong(81)
    1
    >>> pingpong(82)
    0
    >>> pingpong(100)
    -6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    # 迭代解法
    """
    i = 1
    val = 1
    direction = 1
    while i != n:
        i += 1
        val += direction
        if num_eights(i) == 1 or i % 8 == 0:
            direction *= -1
    return val
    """

    def direction(x):
        if x == 1:
            return 1
        if num_eights(x) == 1 or x % 8 == 0:
            return - direction(x - 1)
        return direction(x - 1)

    # 递归解法
    if n == 1:
        return 1
    return pingpong(n - 1) + direction(n - 1)


def missing_digits(n):
    """Given a number a that is in sorted, increasing order,
    return the number of missing digits in n. A missing digit is
    a number between the first and last digit of a that is not in n.
    >>> missing_digits(1248) # 3, 5, 6, 7
    4
    >>> missing_digits(1122) # No missing numbers
    0
    >>> missing_digits(123456) # No missing numbers
    0
    >>> missing_digits(3558) # 4, 6, 7
    3
    >>> missing_digits(35578) # 4, 6
    2
    >>> missing_digits(12456) # 3
    1
    >>> missing_digits(16789) # 2, 3, 4, 5
    4
    >>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8
    7
    >>> missing_digits(4) # No missing numbers between 4 and 4
    0
    >>> from construct_check import check
    >>> # ban while or for loops
    >>> check(HW_SOURCE_FILE, 'missing_digits', ['While', 'For'])
    True
    """
    # 如果小于十直接返回，大于10的话看最后两个数字，如果相等或者只差一，则扔掉最后一位看前面几位，如果相差大于一，则最后一位减一继续递归
    # 可以用 missing_digits(1248) # 3, 5, 6, 7 这个用这个例子手动跑一下看一下代码
    if n < 10:
        return 0
    last_digit = n % 10
    second_last_digit = n // 10 % 10
    if last_digit == second_last_digit or last_digit == second_last_digit + 1:
        return missing_digits(n // 10)
    return missing_digits(n - 1) + 1


def next_largest_coin(coin):
    """Return the next coin. 
    >>> next_largest_coin(1)
    5
    >>> next_largest_coin(5)
    10
    >>> next_largest_coin(10)
    25
    >>> next_largest_coin(2) # Other values return None
    """
    if coin == 1:
        return 5
    elif coin == 5:
        return 10
    elif coin == 10:
        return 25


def count_coins(total):
    """Return the number of ways to make change for total using coins of value of 1, 5, 10, 25.
    >>> count_coins(15)
    6
    >>> count_coins(10)
    4
    >>> count_coins(20)
    9
    >>> count_coins(100) # How many ways to make change for a dollar?
    242
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])                                          
    True
    """

    def func(total, amount):
        if total == 0:
            return 1
        if amount > total:
            return 0
        if total < 0:
            return 0
        if amount == 25:
            return func(total - amount, amount)
        return func(total - amount, amount) + func(total, next_largest_coin(amount))

    return func(total, 1)


from operator import sub, mul


def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    >>> from construct_check import check
    >>> # ban any assignments or recursion
    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
    True
    """
    # 前一个括号是函数声明，后面一个括号是函数调用，类似于func(val)
    # 然后这个时候前一个括号中的f指向的就是后面括号中的递归函数
    # 所以实际返回的就是lambda k: f(f, k)，此时调用时候k就是传进来的参数5
    # 然后就相当于调用f(f, 5)，因为没有办法直接使用函数名，所以只能通过将函数自身当做参数向后传递使用
    return (lambda f: (lambda k: f(f, k)))(lambda f, k: 1 if k == 1 else k * f(f, k - 1))
